/**
 * @param {number} n
 * @param {number} headID
 * @param {number[]} manager
 * @param {number[]} informTime
 * @return {number}
 */
export var numOfMinutes = function (n, headID, manager, informTime) {
  const map = new Map()
  function dfs(id, manager, informTime) {
    if (manager[id] === -1) return informTime[id]
    if (map.has(id)) return map.get(id)
    return informTime[id] + dfs(manager[id], manager, informTime)
  }
  let ans = 0
  for (let i = 0; i < n; i++) {
    if (i === headID) continue
    const minu = dfs(i, manager, informTime)
    map.set(i, minu)
    ans = Math.max(ans, minu)
  }
  return ans
}

/**
 * @param {number} n
 * @param {number} headID
 * @param {number[]} manager
 * @param {number[]} informTime
 * @return {number}
 */
export var numOfMinutes2 = function (n, headID, manager, informTime) {
  const minus = new Array(n).fill(-1)
  function dfs(id) {
    if (id === headID) return 0
    if (minus[id] > -1) return minus[id]
    minus[id] = informTime[manager[id]] + dfs(manager[id])
    return minus[id]
  }
  let ans = 0
  for (let i = 0; i < n; i++) {
    if (i === headID) continue
    ans = Math.max(ans, dfs(i))
  }
  return ans
}
